package sword_offer;

import common.TreeNode;

import java.util.*;

/**
 * @ClassName _32_1_LevelOrderTree
 * @Description: 从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
 * @Author: yongliang.ma
 * @Create_time:2022/10/10 13:25
 */
public class _32_1_LevelOrderTree {

    // 由于不知道具体有多少个节点，所以需要使用动态数组来存储数据，后续再次构造数组
    public int[] levelOrder(TreeNode root) {
        if (root == null)
            return new int[]{};

        Deque<TreeNode> deque = new LinkedList<>();
        List<Integer> target = new ArrayList<>();
        deque.offer(root);
        while (!deque.isEmpty()){
            TreeNode treeNode = deque.poll();
            target.add(treeNode.val);
            if (treeNode.left != null)
                deque.offer(treeNode.left);
            if (treeNode.right != null)
                deque.offer(treeNode.right);
        }

        final int size = target.size();
        int[] nodeVals = new int[size];
        for (int i = 0; i < size; i++) {
            nodeVals[i] = target.get(i);
        }

        return nodeVals;
    }
}
